package com.review.backpack_01;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BP08 {
    //8. 求背包问题的方案
    //输出最优方案
    public int knapsackProblem(int[] c, int[] v, int cap) {
        int[][] dp = new int[c.length + 1][cap + 1], g = new int[c.length + 1][cap + 1];
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= c.length; i++) {
            for (int j = cap; j > 0; j--) {
                if (c[i - 1] <= j) {
                    if (dp[i - 1][j] >= dp[i - 1][j - c[i - 1]] + v[i - 1]) {
                        dp[i][j] = dp[i - 1][j];
                        g[i][j] = 0;
                    } else {
                        dp[i][j] = dp[i - 1][j - c[i - 1]] + v[i - 1];
                        g[i][j] = 1;
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int i = c.length, V = cap;
        while (i > 0) {
            if (g[i][V] == 0) {
                i--;
            } else {
                list.add(i - 1);
                V -= c[i-- - 1];
            }
        }
        Collections.reverse(list);
        System.out.println("已选择物品下标： " + list);
        return dp[c.length][cap];
    }
    public static void main(String[] args) {
        System.out.println(new BP08().knapsackProblem(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}
